By a theorem of Gordon and Hedenmalm, $\varphi$ generates a bounded composition operator on the Hilbert space $\Ht$ of Dirichlet series $\sum_n b_n n^{-s}$ with square-summable coefficients $b_n$ if and only if $\varphi(s)=c_0 s+\psi(s)$, where $c_0$ is a nonnegative integer and $\psi$ a Dirichlet series with the following mapping properties: $\psi$ maps the right half-plane into the half-plane $\Real s >1/2$ if $c_0=0$ and is either identically zero or maps the right half-plane into itself if $c_0$ is positive. It is shown that the $n$th approximation numbers of bounded composition operators on $\Ht$ are bounded below by a constant times $r^n$ for some $00$ when $c_0$ is positive. Both results are best possible. The case when $c_0=0$, $\psi$ is bounded and smooth up to the boundary of the right half-plane, and $\sup \Real \psi=1/2$, is discussed in depth; it includes examples of non-compact operators as well as operators belonging to all Schatten classes $S_p$. For $\varphi(s)=c_1+\sum_{j=1}^d c_{q_j} q_j^{-s}$ with $q_j$ independent integers, it is shown that the $n$th approximation number behaves as $n^{-(d-1)/2}$, possibly up to a factor $(\log n)^{(d-1)/2}$. Estimates rely mainly on a general Hilbert space method involving finite linear combinations of reproducing kernels. A key role is played by a recently developed interpolation method for $\Ht$ using estimates of solutions of the $\bar{\partial}$ equation. Finally, by a transference principle from $H^2$ of the unit disc, explicit examples of compact composition operators with approximation numbers decaying at essentially any sub-exponential rate can be displayed.